#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/11 20:06
# @USER    : Shengji He
# @File    : CountSay.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:

class Solution:
    def countAndSay(self, n: int) -> str:
        """
        The count-and-say sequence is the sequence of integers with the first five terms as following:

        1.     1        \n
        2.     11       \n
        3.     21       \n
        4.     1211     \n
        5.     111221   \n

        - 1 is read off as "one 1" or 11.

        - 11 is read off as "two 1s" or 21.

        - 21 is read off as "one 2, then one 1" or 1211.

        Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.
        You can do so recursively, in other words from the previous member read off the digits,
        counting the number of digits in groups of the same digit.

        Note: Each term of the sequence of integers will be represented as a string.

        Example 1:
            Input: 1

            Output: "1"

            Explanation: This is the base case.
        Example 2:
            Input: 4

            Output: "1211"

            Explanation: For n = 3 the term was "21" in which we have two groups "2" and "1", "2" can be read as "12"
            which means frequency = 1 and value = 2, the same way "1" is read as "11", so the answer is the
            concatenation of "12" and "11" which is "1211".

        :param n: int
        :return: str
        """
        if n == 1:
            return '1'
        else:
            s = ''
            next_s = list(s + self.countAndSay(n - 1))
            if len(next_s) == 1:
                return '1' + next_s[0]
            else:
                count = 1
                sub_s = next_s[0]
                for i in range(1, len(next_s)):
                    if next_s[i] == sub_s:
                        count += 1
                    else:
                        s = s + str(count) + sub_s
                        count = 1
                        sub_s = next_s[i]
                return s + str(count) + sub_s


if __name__ == '__main__':
    S = Solution()
    n = 7
    print(S.countAndSay(n))
    print('done')
